#pragma warning(disable:4996)
#pragma warning(disable:6031)
#pragma warning(disable:6011)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

namespace Y190618_exam_02_3_5_Reversing_Linked_List {
int main();

typedef int ElementType;
typedef struct DataNode* PtrDataNode;
struct DataNode {
	int address;
	int value;
	int next;
};
DataNode g_datas[10001];

typedef struct LNode* LinkedList;
struct LNode {
	PtrDataNode data;
	LinkedList next;
};

void input_ANK(int* address, int* N, int* K);
void input_datas(int n);
void print_g_datas(int n);
PtrDataNode find_data(int address, int n);
LinkedList build_list(int &n, int address);
void print_list(LinkedList L);
LinkedList reverse_list(LinkedList L, int N, int K);

LinkedList create_list(PtrDataNode data) {
	LinkedList l = (LinkedList)malloc(sizeof(struct LNode));
	l->data = data;
	l->next = NULL;
	return l;
}

void free_list(LinkedList L) {
	LinkedList temp;
	while (L)
	{
		temp = L->next;
		free(L);
		L = temp;
	}
}

int main()
{
	int first, N, K;
	input_ANK(&first, &N, &K);
	input_datas(N);
	LinkedList L = build_list(N, first);
	reverse_list(L, N, K);
	print_list(L);
	free_list(L);
	return 0;
}

void input_ANK(int* address, int* N, int* K)
{
	scanf("%d %d %d", address, N, K);
}

void input_datas(int n)
{
	PtrDataNode data = g_datas;
	for (int i = 0; i < n; ++i)
	{
		scanf("%d %d %d", &data->address, &data->value, &data->next);
		//scanf("%d %d %d", &(data->address), &(data->value), &(data->next));
		data++;

	}
}

PtrDataNode find_data(int address, int n)
{
	for (int i = 0; i < n; ++i)
	{
		if (g_datas[i].address == address)
			return &g_datas[i];
	}
	return NULL;
}

LinkedList build_list(int &n, int address)
{
	LinkedList L = create_list(NULL);
	LinkedList head = L;
	LinkedList list_node;
	int n2 = 0;
	
	PtrDataNode data = g_datas;
	int i = 0;
	while (address != -1 && i++<n)
	{
		data = find_data(address, n);
		list_node = create_list(data);
		head->next = list_node;
		head = head->next;
		address = data->next;
		n2++;
	}
	n = n2;
	return L;
}

LinkedList reverse_list(LinkedList L, int N, int K) {
	if (K < 1 || N < 1)
		return L;
	LinkedList head = L;
	LinkedList head0 = L;
	LinkedList new_node = NULL;
	LinkedList old_node = NULL;
	LinkedList tmp_node = NULL;
	int j;
	for (int i = 0; i <= N - K; i += K) {
		j = 1;
		new_node = head->next;
		old_node = new_node->next;
		tmp_node = old_node->next;
		while (j++ < K)
		{
			old_node->next = new_node;
			new_node = old_node;
			old_node = tmp_node;
			if (old_node)
				tmp_node = tmp_node->next;
		}
		head0 = head->next;
		head0->next = old_node;
		head->next = new_node;
		head = head0;
	}
	return L;
}

void print_list(LinkedList L)
{
	LinkedList head = L->next;
	PtrDataNode data = NULL;
	while (head && head->next)
	{
		data = head->data;
		printf("%05d %d %05d\n", data->address, data->value, head->next->data->address);
		head = head->next;
	}
	data = head->data;
	printf("%05d %d -1", data->address, data->value);
}

void print_g_datas(int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("\n%05d %d %05d", g_datas[i].address, g_datas[i].value, g_datas[i].next);
	}
}

}

int main_Y190618_exam_02_3_5_Reversing_Linked_List()
{
	return Y190618_exam_02_3_5_Reversing_Linked_List::main();
}